package com.ljy.my_study.lintcode.K数之和;

import java.util.HashSet;
import java.util.Set;

/** 
* @author James
* @date 2018年10月9日 
*/
public class 两数之和 {
	public static void main(String[] args) {
//		int[] nums= {1,3,4,5,6,8,11,14,16,19,20,23,25,28,30,33,34,36,39,41,43,45,46,48,51,53,55,56,58,59,60};
//		int[] nums= {1,3,4,5,6,8,11,14,16,19,20,23,25,28,30,33,34,36,39,41,43,45,46,48,51,53,55,56,58,59,60};
//		System.out.println(kSum(nums,26,811));
//		int[] nums= {1,3,6,7,8,10,13,15,18,21,22,23,25,28,29,32,34,35,36,37,39,42,44,47,49,50,53,55,58,59,61,64};
//		System.out.println(kSum(nums,14,348));
		int[] nums= {1,3,4,5,8,10,11,12,14,17,20,22,24,25,28,30,31,34,35,37,38,40,42,44,45,48,51,54,56,59,60,61,63,66};
		System.out.println(kSum(nums,24,842));
//		int[] nums= {1,2,4,5,7,8,10,11,12,13,15};
//		System.out.println(kSum(nums,3,16));
	}
	
	public static int twoSum(int[] A, int target) {
		int count=0;
		int len=A.length;
		out:for(int i=0;i<len-1;i++) {
			int n=target-A[i];
			for(int j=i+1;j<len;j++) {
				if(n+A[j]>target) {
					continue out;
				}
				if(n+A[j]==target) {
					count++;
				}
			}
		}
		return count;
	}
	
	public static int kSum(int[] A, int k, int target) {
		int n=0;
		int index=0;
		Set<Integer> set=new HashSet<>();
		for(int i=0;i<A.length;i++) {
			set.add(A[i]);
		}
		if(k==1&&set.contains(target)) {
			return 1;
		}
		while(index<=A.length-k) {
			if(target-A[index]<=A[index]) {
				break;
			}
			n+=kSum(A,k-1,target-A[index],index+1,set);
			index++;
		}
		return n;
	}
	
	public static int kSum(int[] A,int k,int target,int index,Set<Integer> set) {
		int n=0;
		if(k==1&&set.contains(target)&&A[index]<=target) {
			return 1;
		}else if(k<=1) {
			return 0;
		}
		while(index<=A.length-k) {
			if(target-A[index]<=A[index]) {
				return n;
			}
			n+=kSum(A,k-1,target-A[index],index+1,set);
			index++;
		}
		return n;
	}
}
